Induksi Matematika

Efek Domino

Perhatikan bahwa sesuai teori dalam fisika:

"Jika $k$ jatuh, maka $k+1$ jatuh."

Perhatikan pula beberapa teorema dalam matematika seperti:

"jika $a=2$, maka $a+1=2+1$"

"$a>1\Rightarrow \dfrac{1}{a}<1$"

"$p>1\Rightarrow p+1>1$"

"Jika $k^3+2k$ habis dibagi 3, maka $(k+1)^3+2(k+1)$ habis dibagi 3"

Kalimat tertutup $P(n)$

Kalimat tertutup merupakan kalimat yang bisa dinilai kebenarannya.

Contoh kalimat tertutup:

"Kitab suci ummat Islam adalah Al-Qur'an."

"$\sin^2{x}+\cos^2{x}=1,\forall x\in\mathbb{R}$."

"Pada tanggal 1 Januari 2017 lalu matahari terbit dari barat."

"Presiden ke-4 Republik Indonesia adalah Bapak B.J. Habibie."

Misal $P(n)$ didefinisikan sebagai:
$P(n):$ "$n$ adalah bilangan yang kurang dari $10$."

$P(1)$ adalah pernyataan:

"1 adalah bilangan yang kurang dari $10$."

$\therefore\; P(1)$ benar.

$P(17)$ adalah pernyataan:

"17 adalah bilangan yang kurang dari $10$."

$\therefore\; P(17)$ salah.

Misal $P(n)$ didefinisikan sebagai:
$P(n):$ "Domino ke-$n$ (seperti dalam simulasi sebelumnya) jatuh."

Misal domino ke-1 dijatuhkan ke arah domino-2.

$P(1)$ adalah pernyataan:

"Domino ke-1 jatuh."

$\therefore\; P(1)$ benar.

$P(100)$ adalah pernyataan:

"Domino ke-100 jatuh."

$\therefore\; P(100)$ benar. Dari sifat domino jatuh.

$P(n):$ "Domino ke-$n$ jatuh." adalah salah satu contoh dimana

Jika $P(k)$ benar, maka $P(k+1)$ benar.

$P(n):$ " $n>19.$" adalah contoh lain dimana

Jika $P(k)$ benar, maka $P(k+1)$ benar.

yaitu: Jika $P(k)$ benar, maka $k>19$ dan diperoleh

$k+1>19+1=20>19$

Dengan demikian $k+1>19$, yang merupakan $P(k+1)$

Prinsip Induksi Matematika

Misal $P(n)$ suatu pernyataan bilangan asli dan

$P(1)$ benar,
Jika $P(k)$ benar maka $P(k+1)$ benar,

maka $P(n)$ benar untuk semua $n\in\mathbb{N}$.

Tunjukkan bahwa:

$1+3+5+\cdots+(2n-1)=n^2$.
$n^3+2n$ habis dibagi 3 untuk setiap $n\in\mathbb{N}$.
Semua bilangan asli kurang dari 10.

Misal $P(n):$"$1+3+5+\cdots+(2n-1)=n^2$".
Maka $P(1)$:"$1=1^2$".
$\therefore\; P(1)$ benar

Asumsikan $P(k)$ benar, artinya $$1+3+5+\cdots+(2k-1)=k^2.$$

Tambahkan $2(k+1)-1$ pada kedua ruas, sehingga diperoleh \[ \begin{eqnarray} 1+3+5+\cdots+(2k-1)+(2(k+1)-1)&=&k^2+2(k+1)-1\\ &=&k^2+2k+1\\ &=&(k+1)^2\\ \end{eqnarray} \] $\therefore\;P(k+1)$ benar.

Dengan demikian $1+3+5+\cdots+2n-1=n^2, \forall n\in\mathbb{N}$.

Telah kita ketahui bahwa $P(k)$ benar. Selanjutnya akan kita periksa apakah pernyataan berikut terpenuhi.

"Jika $P(k)$ benar, maka $P(k+1)$ benar"

$P(k+1)$ adalah pernyataan \[ \underbrace{\underbrace{1+3+5+\cdots+(2k-1)}_{\text{sudah diketahui dari $P(k)$}}+(2(k+1)-1)}_{\text{untuk ditunjukkan apakah sama dengan $(k+1)^2$}}=(k+1)^2\\ \] Sehingga perlu kita tambahkan $2(k+1)-1$ di ruas kiri $P(k)$

Telah kita ketahui bahwa $P(k)$ benar. Selanjutnya akan kita periksa apakah pernyataan berikut terpenuhi.

"Jika $P(k)$ benar, maka $P(k+1)$ benar"

$P(k+1)$ adalah pernyataan:

"$(k+1)^3+2(k+1)$ habis dibagi 3"

atau dengan kata lain

$(k+1)^3+2(k+1)=3P$ untuk suatu $P\in\mathbb{Z}$

Oleh karena itu akan kita lihat apakah $(k+1)^3+2(k+1)$ habis dibagi 3 jika diketahui $k^3+2k$ habis dibagi 3.

Misal $P(n):$"$n^3+2n$ habis dibagi 3".
Maka $P(1)$:"$1^3+2\cdot 1$ habis dibagi 3".
$\therefore\; P(1)$ benar

Asumsikan $P(k)$ benar, artinya $k^3+2k$ habis dibagi 3. Dengan kata lain $k^3+2k = 3M, \text{untuk suatu } M\in\mathbb{Z}.$

Kita peroleh: \[ \begin{eqnarray}(k+1)^3+2(k+1)&=&(k^3+3k^2+3k+1)+(2k+2)\\ &=&k^3+2k+3k^2+k+1+2k+2\\ &=&(k^3+2k)+3(k^2+k+1)\\ &=&3(M+k^2+k+1) \end{eqnarray} \] $\therefore\;P(k+1)$ benar.

Dengan demikian $n^3+2n$ habis dibagi 3, $\forall n\in\mathbb{N}$.

Misal $P(n):$"$n < 10$".
Maka $P(1)$:"$1 < 10$".
$\therefore\; P(1)$ benar

Asumsikan $P(k)$ benar, artinya $k < 10$.

Hingga tahap ini kita TIDAK bisa membuktikan

"Jika $P(k)$ benar, maka $P(k+1)$ benar."

atau dengan kata lain

"Jika $k<10$ maka $k+1<10$."

Sebagai contoh, pilih $k=9$.

Prinsip Induksi Matematika 2

Misal $P(n)$ suatu pernyataan bilangan asli, $n_0\in\mathbb{N}$ dan

$P(n_0)$ benar,
Jika $P(k)$ benar maka $P(k+1)$ benar,

maka $P(n)$ benar untuk semua $n\in\mathbb{N}, n\geq n_0$.

Telah kita ketahui bahwa $P(k)$ benar. Selanjutnya akan kita periksa apakah pernyataan berikut terpenuhi.

"Jika $P(k)$ benar, maka $P(k+1)$ benar"

$P(k+1)$ adalah pernyataan: "$(k+1)!>2^{k+1}$" atau $$"k!(k+1)>2^{k+1}".$$
Karena $k!>2^k$, maka $k!(k+1)>2^k(k+1)$.

Di sisi lain, untuk $k\geq 4$ kita peroleh $(k+1)>2$.
Sehingga $k!(k+1)>2^k(k+1)>2^k\cdot2=2^{k+1}$

Buktikan bahwa: $n!>2^n,\;\forall n\in\mathbb{N}, n\geq4$

Misal $P(n)$: "$n!>2^n$"

Maka $P(4)$: "$4!>2^4$"
$\therefore\;P(4)$ benar.

Asumsikan $P(k)$ benar, artinya $k!>2^k$.

Maka kita peroleh \[ \begin{eqnarray} k!(k+1) &>& 2^k(k+1)\\ (k+1)! &>& 2^{k+1} \end{eqnarray} \] $\therefore\;P(k+1)$ benar.

Dengan demikian $n!>2^n,\;\forall n\in\mathbb{N}, n\geq4$.

Buktikan pernyataan berikut menggunakan induksi matematika.

$1+2+3+\cdots+n=\frac{n(n+1)}{2}$
$x^n-y^n$ habis dibagi $x-y$, $\forall n\in\mathbb{N}$
$n^3+3n^2+2n$ habis dibagi 3 untuk setiap $n\in\mathbb{N}$
$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$
1. Misal $P(n)$: "$2+4+6+\cdots+2n=n^2+n+2$". Tunjukkan bahwa jika $P(k)$ benar maka $P(k+1)$ benar.
2. Dari poin (a), apakah berarti $P(n)$ benar untuk semua $n\in\mathbb{N}$?